package com.platform.modules.alg.alglib.p155;

public class P155 {
    private int maxn = 100;
    private int maxm = 10000;
    int n;
    int ss[] = new int[maxn];
    int sa[] = new int[maxn];
    int wa[] = new int[maxn];
    int wb[] = new int[maxn];
    int wv[] = new int[maxn];
    int c[] = new int[maxm]; // c[]用于基数排序统计

    boolean cmp(int r[], int a, int b, int l) {
        return (r[a] == r[b]) && (r[a + l] == r[b + l]);
    }

    // 打印数组
    void print(int s[], int t) {
        for (int i = 0; i < t; i++)
            output += s[i] + "\t";
        output += "\n";
    }

    // 交换两个数组的内容 https://blog.csdn.net/m0_56793367/article/details/115599564
    public static void swap(int[] array1, int[] array2) {
        int tmp = 0;
        for (int i = 0; i < array1.length; i++) {
            tmp = array1[i];
            array1[i] = array2[i];
            array2[i] = tmp;
        }
    }

    void print_suffix(String s, int sa[]) {
        for (int i = 1; i <= n; i++)
            output += s.substring(sa[i]) + "\n";
    }

    void da(int r[], int sa[], int n, int m) {
        int i, k, p;
        int x[] = wa;
        int y[] = wb;
        for (i = 0; i < m; i++) // 基数排序
            c[i] = 0;
        for (i = 0; i < n; i++)
            c[x[i] = r[i]]++;
        for (i = 1; i < m; i++)
            c[i] += c[i - 1];
        for (i = n - 1; i >= 0; i--)
            sa[--c[x[i]]] = i;
        output += "初始化排序结果：\n";
        output += "rk:\t";
        print(x, n);
        output += "sa:\t";
        print(sa, n);
        for (k = 1; k <= n; k <<= 1) {
            // 直接利用 sa 排序第二关键字
            p = 0;
            for (i = n - k; i < n; i++)
                y[p++] = i; // 补零的位置下标排在最前面
            for (i = 0; i < n; i++)
                if (sa[i] >= k)
                    y[p++] = sa[i] - k;
            output += "第二关键字排序结果：\n";
            output += "y:\t";
            print(y, n);
            // 基数排序第一关键字
            for (i = 0; i < n; i++)
                wv[i] = x[y[i]]; // 将第二关键字排序结果转换为名次，进行排序
            for (i = 0; i < m; i++)
                c[i] = 0;
            for (i = 0; i < n; i++)
                c[wv[i]]++;
            for (i = 1; i < m; i++)
                c[i] += c[i - 1];
            for (i = n - 1; i >= 0; i--)
                sa[--c[wv[i]]] = y[i];
            output += "x[y[i]]:";
            print(wv, n);
            output += "sa:\t";
            print(sa, n);
            // 根据 sa 和 x 数组，重新计算新的x数组
            swap(x, y); // y 数组已经没有用，更新x需要使用x本身数据，因此放入y使用
            p = 1;
            x[sa[0]] = 0;
            for (i = 1; i < n; i++)
                x[sa[i]] = cmp(y, sa[i - 1], sa[i], k) ? p - 1 : p++;
            output += "第" + k + "次排序结果：\n";
            output += "rk:\t";
            print(x, n);
            output += "sa:\t";
            print(sa, n);
            if (p >= n)//排序结束
                break;
            m = p;
        }
    }
    // 名称数组
    int rank[] = new int[maxn];
    // 高度数组
    int height[] = new int[maxn];

    void calheight(int r[], int sa[], int n) {
        int i, j, k = 0;
        for (i = 1; i <= n; i++)
            rank[sa[i]] = i;
        output += "名次数组：\n";
        print(rank, n);
        for (i = 0; i < n; i++) {
            if (k > 0)
                k--;
            j = sa[rank[i] - 1];
            while (r[i + k] == r[j + k])
                k++;
            height[rank[i]] = k;
        }
        output += "高度数组：\n";

        int height1[] = new int[maxn];
        for (int count = 0; count < height.length - 1; count++) {
            height1[count] = height[count + 1];
        }

        print(height1, n);
    }

    public String output = "";

    public String cal(String input) {
        String[] line = input.split("\n");
        // aabaaaab
        String s = line[0];
        n = s.length();
        for (int i = 0; i < n; i++)
            ss[i] = s.charAt(i) - 'a' + 1;
        ss[n] = 0;
        da(ss, sa, n + 1, maxm);
        print_suffix(s, sa);
        calheight(ss, sa, n);
        return output;
    }
}
